package com.minglan.leetcode.java.solution2103;

import java.util.ArrayList;
import java.util.List;

/*
 * 2021.3.8
 * 132. 分割回文串 II
示例 1：

输入：s = "aab"
输出：1
解释：只需一次分割就可将 s 分割成 ["aa","b"] 这样两个回文子串。
示例 2：

输入：s = "a"
输出：0
示例 3：

输入：s = "ab"
输出：1

 */
public class MinCut {

	int minCut(String s) {

		int n = s.length();
		char[] chars = s.toCharArray();
		int[] tmp = new int[n];
		for (int i = 0; i < n; i++) {
			int left = i, right = i;
			int v = i - 1 < 0 ? 1 : tmp[i - 1] + 1;
			tmp[i] = tmp[i] > 0 ? Math.min(tmp[i], v) : v;
			while (right + 1 < n && chars[left] == chars[right + 1]) {
				right++;
				tmp[right] = tmp[right] > 0 ? Math.min(v, tmp[right]) : v;
			}
			while (left - 1 >= 0 && right + 1 < n && chars[left - 1] == chars[right + 1]) {
				left--;
				right++;
				int pre = left - 1 < 0 ? 0 : tmp[left - 1];
				tmp[right] = tmp[right] > 0 ? Math.min(pre + 1, tmp[right]) : pre + 1;
			}
		}
		return tmp[n - 1] - 1;

	}

	public static void main(String[] args) {
		MinCut m = new MinCut();
		System.out.println(m.minCut("ababababababababababababcbabababababababababababa"));

	}

}
